package string;

import org.junit.Test;

public class String_ {
    /**
     * 最长公共前缀
     */
    public String longestCommonPrefix(String[] arr) {
        //只有一个情况
        if(arr.length == 1){
            return arr[0];
        }
        StringBuilder sb = new StringBuilder();

        //应求出最小长度
        int mlength = arr[0].length();
        for (int i = 1; i < arr.length; i++) {
            if(arr[i].length()<mlength){
                mlength = arr[i].length();
            }
        }
        label:    for(int j=0;j<mlength;j++){
            for(int k = 1; k <arr.length; k++){
                if(arr[k].charAt(j)!=arr[0].charAt(j)){
                    break label;
                }
                if(k==arr.length - 1){
                    sb.append(arr[0].charAt(j));
                }
            }
        }
        return sb.toString();
    }



    /**
     * 最长回文子串
     */
    public String longestPalindrome(String s) {
        //遍历
        //对于每个元素, 后往前, 判断是否为回文
        //若果不等,前移动;
        //如果等于,试着前移,成功则记录,不成功继续前移
        //cbbd
        int l=0;int r = s.length()-1;
        int lindex ;int rindex ;
        int mlindex = 0;int mrindex = 0;
        for(int i = 0; i < s.length(); i++){
            l = i;lindex = i;
            for(int j = s.length()-1; j >i; j--){
                r = j;rindex = j;//待改进:匹配失败记录提供效率
                l = i;
                int failIndex = s.length();
                while(l<r) {
                    if(r >= failIndex){
                        break;
                    }
                    if (s.charAt(l) != s.charAt(r)) {
                        failIndex = r;
                        break;
                    }
                    l++;
                    r--;
                }
                if (l>=r){
                    if(rindex - lindex>mrindex-mlindex)
                    {
                        mrindex = rindex ;
                        mlindex = lindex;
                    }
                }

            }

        }
        return s.substring(mlindex,mrindex+1);

    }

    /**
     * 翻转字符串里的单词
     */
    public String reverseWords(String s) {
        boolean addable = true;
        int rIndex = 0;
        StringBuilder sb = new StringBuilder();
        for(int i=s.length()-1;i>=0;i--){
            if (s.charAt(i)!=' ' && addable){
                rIndex = i;
                addable = false;
            }
            else if (s.charAt(i)==' '  && !addable){
                sb.append(s.substring(i + 1,rIndex+1)+" ");
                addable = true;
            }
            if ( i == 0  && !addable){
                sb.append(s.substring(i,rIndex+1)+" ");
                addable = true;
            }

        }
        return sb.toString().substring(0,sb.length() - 1);


    }

    /**
     * 实现strStr()
     * (KMP算法)
     */
    public int strStr(String str, String subStr) {
        if(str.length() < subStr.length()){
            return -1;
        }
        int next[] = new int[subStr.length()];
        Getnext(next, subStr); //获得next数组
        int i = 0, start = 0;//两个指针
        while(i < str.length()) {
            while (str.charAt(i) == subStr.charAt(start)) {
                i++;
                start++;
                if(start == subStr.length()) {
                    return i - start;
                }
                if( i== str.length()){
                    return -1;
                }
            }
            if(start == 0){i++;}//next[0]==-1处理
            else {
                start = next[start];
            }
        }
        return -1;
    }
    void Getnext(int next[],String t){
        //定义k:匹配度(越大代表越匹配);
        //定义j:匹配的当前索引
        int j=0,k=-1;
        next[0]=-1;
        while(j<t.length()-1)
        //推导结束再看,会发现刚刚好
        {
            if(k == -1 || t.charAt(j) == t.charAt(k))
            //匹配度=-1:下一个;
            //匹配度=当前索引:下一个索引=当前索引+1=当前匹配进度+1
            //然后直接下一个,因为next数组相邻大小<=1
            {
                j++;k++;//k=0:匹配度为0,要想变长首先与t[0]匹配
                next[j] = k;//next后,记录这串的匹配度
            }
            //匹配失败:降级
            else k = next[k];
        }
    }
    public void reverseString(char[] s) {
        int left = 0;
        int right =s.length - 1;
        while (left < right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }

    }
//    public String reverseStr(String s, int k) {
//        // abcdefg 2
//        char[] arr = s.toCharArray();
//        int index = 0;
//        //i未到末尾
//        for (int i = k * 2 - 1; i < s.length(); i += k * 2) {
//            //先翻转
//            reverse(arr, i - k * 2 + 1, i - k);
//            //其他不变
//        }
//        //到达末尾
//        int j = s.length() % (k * 2);
//        if (j < k) {
//            reverse(arr,s.length() - j ,s.length() - 1);
//
//        } else  {
//            reverse(arr,s.length() - j ,s.length() - j + k - 1);
//        }
//        StringBuilder sb = new StringBuilder();
//        for(int i : arr){
//            sb.append(i);
//        }
//        return sb.toString();
//    }
    public void reverse(char[] arr, int i, int j) {
        while(i < j) {
            char temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    public String reverseStr(String s, int k) {
        // abcdefg 2
        char[] arr = s.toCharArray();
        //i未到末尾
        for (int i = 0; i < s.length(); i += k * 2) {
            //先翻转
            if(i + k - 1 >= s.length()){
                reverse(arr, i, s.length() - 1);
            }
            reverse(arr, i, i + k - 1);
            //其他不变
        }
        //到达末尾

        StringBuilder sb = new StringBuilder();
        for(char i : arr){
            sb.append(i);
        }
        return sb.toString();
    }

    public String reverseWords2(String s) {
        String[] strs = arrTrim(s).split(" ");
        StringBuilder sb = new StringBuilder();
        for(int i = strs.length - 1; i >= 0; i-- ){
            if(!strs[i].isBlank()){
                sb.append(arrTrim(strs[i]));
                if(i != 0)   sb.append(" ");
            }
        }
        return sb.toString();
    }
    public String arrTrim(String str) {

        int left = 0;
        int right = str.length() - 1;
        while (str.charAt(left) == ' ') left++;
        while (str.charAt(right) == ' ') right--;
        return str.substring(left,right+1);
    }
    public String reverseWords3(String s) {
        String[] str = s.trim().split(" ");
        StringBuilder sb = new StringBuilder();
        for(int i = str.length - 1; i >= 0; i--){
            if(!str[i].equals("")){
                sb.append(str[i]);
            }
        }
        return sb.toString();


    }
    public int strStr1(String haystack, String needle) {
        int i = 0, j = 0;
        int[] next =next(needle);
        while(i < haystack.length()){
            if (haystack.charAt(i) != needle.charAt(j)) {
                if(j == 0) continue;
                j = next[j];
            }
            else {
                if (j == needle.length() - 1) {
                    return i;
                }
                i++;
                j++;
            }
        }
        return -1;

    }
    public int[] next(String s) {
        int[]  next = new int[s.length()+1];
        next[0] = -1;
        int i = 0;
        int j = -1;
        while(i < s.length()) {
            if (j == -1 || s.charAt(j) == s.charAt(i)) {
                j++;
                i++;
                next[i] = j;
            }
            else {
                j = next[j];
            }
        }
        return next;
    }
//    @Test
//    public void repeatedSubstringPattern() {
//        String s ="abcabcabc";
//        if(s.substring(0,s.length() / 2).equals(s.substring(s.length()/2))) System.out.println("t");
//        int n = 2;
//        while(n <= s.length() / 2){
//            if(s.length() % n != 0) n++;continue;
//            for(int i = n;i < s.length(); i += n){
//                if(!s.substring(i - n,i).equals(s.substring(i,i+n))) break;
//                if(i+n >=s.length()) System.out.println("t");
//            }
//            n++;
//        }
//        System.out.println("f");;
//    }
}
